// 2025/10/23
// 蛇梯棋

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        vector<int> line(n * n + 1);
        for(int i = ((n % 2 == 0) ? 0 : 1); i < n; i += 2)
        {
            reverse(board[i].begin(), board[i].end());
        }
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = 0; j < n; j++)
            {
                int pos = (n - 1 - i) * n + (j + 1);
                line[pos] = board[i][j];
            }
        }

        // 位置/步数
        queue<pair<int, int>> q;
        q.emplace(1, 0);
        while(!q.empty())
        {
            auto cur = q.front();
            q.pop();
            if(cur.first == n * n)
                return cur.second;
            for(int pos = cur.first + 1; pos <= min(cur.first + 6, n * n); pos++)
            {
                if(line[pos] > 0)
                {
                    q.emplace(line[pos], cur.second + 1);
                }
                else if(line[pos] == -1)
                {
                    q.emplace(pos, cur.second + 1);
                }
                line[pos] = 0;
            }
        }
        return -1;
    }
};